tool

class_name MyMeshBuilder

static func _build_bottom_face(v: PoolVector3Array, face_flags: int, st: SurfaceTool):
	if (face_flags & 0x40) == 0:
		if (face_flags & 0x100) == 0:
			st.add_triangle_fan(PoolVector3Array([v[0], v[2], v[3]]))
		if (face_flags & 0x80) == 0:
			st.add_triangle_fan(PoolVector3Array([v[0], v[3], v[1]]))
	else:
		if (face_flags & 0x100) == 0:
			st.add_triangle_fan(PoolVector3Array([v[0], v[2], v[1]]))
		if (face_flags & 0x80) == 0:
			st.add_triangle_fan(PoolVector3Array([v[2], v[3], v[1]]))

static func _build_right_triangle(v: PoolVector3Array, decoration_size: float, \
		flags: int, \
		st: SurfaceTool, st2: SurfaceTool):
	if flags == 0:
		st.add_triangle_fan(v)
	elif (flags & 0x10) == 0:
		v.append(lerp(v[0], v[1], decoration_size))
		v.append(lerp(v[1], v[0], decoration_size))
		v.append(lerp(v[0], v[2], decoration_size))
		v.append(v[3] + v[5] - v[0])
		v.append(lerp(v[1], v[2], decoration_size))
		v.append(lerp(v[2], v[0], decoration_size))
		v.append(lerp(v[2], v[1], decoration_size))
		match flags & 0x2F:
			0x1:
				st2.add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[1], v[6]]))
				st.add_triangle_fan(PoolVector3Array([v[6], v[1], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[6], v[2]]))
			0x4:
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[7]]))
				st.add_triangle_fan(PoolVector3Array([v[0], v[4], v[7], v[2]]))
			0x5:
				st2.add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[7]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[4], v[7], v[6]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[7], v[2]]))
			0x7:
				st2.add_triangle_fan(PoolVector3Array([v[0], v[1], v[7], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[7], v[2]]))
			0x20:
				st2.add_triangle_fan(PoolVector3Array([v[8], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[0], v[1], v[9], v[8]]))
			0x21:
				st2.add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				st2.add_triangle_fan(PoolVector3Array([v[8], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[6], v[9], v[8]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[1], v[9]]))
			0x24:
				st2.add_triangle_fan(PoolVector3Array([v[8], v[9], v[2]]))
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[7]]))
				st.add_triangle_fan(PoolVector3Array([v[0], v[4], v[7], v[9], v[8]]))
			0x27:
				st2.add_triangle_fan(PoolVector3Array([v[8], v[9], v[2]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[1], v[7], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[7], v[9], v[8]]))
			0x29:
				st2.add_triangle_fan(PoolVector3Array([v[0], v[3], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[1], v[9]]))
			0x2D:
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[7]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[3], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[4], v[7], v[9]]))
			0x2F:
				st2.add_triangle_fan(PoolVector3Array([v[0], v[1], v[7], v[6]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[6], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[6], v[7], v[9]]))
			_:
				(st2 if (flags & 0x1) != 0 else st).add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				(st2 if (flags & 0x2) != 0 else st).add_triangle_fan(PoolVector3Array([v[3], v[4], v[7], v[6]]))
				(st2 if (flags & 0x4) != 0 else st).add_triangle_fan(PoolVector3Array([v[4], v[1], v[7]]))
				(st2 if (flags & 0x8) != 0 else st).add_triangle_fan(PoolVector3Array([v[5], v[6], v[9], v[8]]))
				st.add_triangle_fan(PoolVector3Array([v[6], v[7], v[9]]))
				(st2 if (flags & 0x20) != 0 else st).add_triangle_fan(PoolVector3Array([v[8], v[9], v[2]]))
	else:
		v.append(lerp(v[0], v[1], decoration_size))
		v.append(lerp(v[1], v[0], decoration_size))
		v.append(lerp(v[0], v[2], decoration_size))
		v.append(v[3] + v[5] - v[0])
		v.append((v[2] - v[1]) * decoration_size + v[4])
		v.append(lerp(v[2], v[0], decoration_size))
		v.append((v[1] - v[2]) * decoration_size + v[8])
		flags |= (flags & 0x4) >> 1
		flags |= (flags & 0x20) >> 2
		match flags & 0xB:
			0x0:
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[2], v[8]]))
				st.add_triangle_fan(PoolVector3Array([v[0], v[4], v[8]]))
			0x1:
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[2], v[8]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[4], v[6]]))
				st.add_triangle_fan(PoolVector3Array([v[6], v[4], v[8]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[6], v[8]]))
			0x2:
				st2.add_triangle_fan(PoolVector3Array([v[7], v[1], v[2], v[8]]))
				st2.add_triangle_fan(PoolVector3Array([v[3], v[1], v[7], v[6]]))
				st.add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[7], v[8]]))
			0x3:
				st2.add_triangle_fan(PoolVector3Array([v[7], v[1], v[2], v[8]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[1], v[7], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[5], v[7], v[8]]))
			0x8:
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[2], v[9]]))
				st2.add_triangle_fan(PoolVector3Array([v[5], v[6], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[4], v[9]]))
			0x9:
				st2.add_triangle_fan(PoolVector3Array([v[4], v[1], v[2], v[9]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[3], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[3], v[4], v[9]]))
			0xA:
				st2.add_triangle_fan(PoolVector3Array([v[7], v[1], v[2], v[9]]))
				st2.add_triangle_fan(PoolVector3Array([v[3], v[1], v[7], v[6]]))
				st2.add_triangle_fan(PoolVector3Array([v[5], v[6], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[0], v[3], v[6], v[5]]))
				st.add_triangle_fan(PoolVector3Array([v[6], v[7], v[9]]))
			0xB:
				st2.add_triangle_fan(PoolVector3Array([v[7], v[1], v[2], v[9]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[1], v[7], v[6]]))
				st2.add_triangle_fan(PoolVector3Array([v[0], v[6], v[9], v[2]]))
				st.add_triangle_fan(PoolVector3Array([v[6], v[7], v[9]]))

static func _build_top_face(v: PoolVector3Array, decoration_size: float, \
		decoration_flags: int, face_flags: int, \
		st: SurfaceTool, st2: SurfaceTool):
	if (face_flags & 0x40) == 0:
		if (face_flags & 0x100) == 0:
			_build_right_triangle(PoolVector3Array([v[6], v[4], v[7]]), decoration_size, \
					((decoration_flags & 0x40) >> 6) | \
					((decoration_flags & 0x8) >> 2) | \
					((decoration_flags & 0x1) << 2) | \
					((decoration_flags & 0x80) >> 4) | \
					(decoration_flags & 0x10) | \
					((decoration_flags & 0x100) >> 3) , \
					st, st2)
		if (face_flags & 0x80) == 0:
			_build_right_triangle(PoolVector3Array([v[5], v[7], v[4]]), decoration_size, \
					((decoration_flags & 0x4) >> 2) | \
					((decoration_flags & 0x20) >> 4) | \
					((decoration_flags & 0x100) >> 6) | \
					((decoration_flags & 0x2) << 2) | \
					(decoration_flags & 0x10) | \
					((decoration_flags & 0x1) << 5) , \
					st, st2)
	else:
		if (face_flags & 0x100) == 0:
			_build_right_triangle(PoolVector3Array([v[4], v[5], v[6]]), decoration_size, \
					(decoration_flags & 0x1F) | ((decoration_flags & 0x40) >> 1), \
					st, st2)
		if (face_flags & 0x80) == 0:
			_build_right_triangle(PoolVector3Array([v[7], v[6], v[5]]), decoration_size, \
					((decoration_flags & 0x100) >> 8) | \
					((decoration_flags & 0x80) >> 6) | \
					((decoration_flags & 0x40) >> 4) | \
					((decoration_flags & 0x20) >> 2) | \
					(decoration_flags & 0x10) | \
					((decoration_flags & 0x4) << 3) , \
					st, st2)

static func build_cube(param: Dictionary, st: SurfaceTool, st2: SurfaceTool, collision_shapes: Array):
	st.add_smooth_group(false)
	if st2 != null:
		st2.add_smooth_group(false)

	# x0 z0 x3 z3 [x1 z1]
	var rect: PoolVector2Array = param.get("rect", PoolVector2Array())

	if rect.size() < 2:
		rect = PoolVector2Array([Vector2(0.0, 0.0), Vector2(2.0, 2.0)])

	# y0-y7
	var ys: PoolRealArray = param.get("ys", PoolRealArray())

	if ys.size() < 2:
		ys = PoolRealArray([0.0, 2.0])

	if ys.size() < 8:
		ys = PoolRealArray([ys[0], ys[0], ys[0], ys[0], ys[1], ys[1], ys[1], ys[1]])

	# relative size, 0-0.5
	var decoration_size: float = param.get("decoration_size", 0.2)

	# bit 0-8: show decoration
	var decoration_flags: int = param.get("decoration_flags", 0)

	# bit 0-5: hide faces
	# bit 6: flip top face quad
	# bit 7-8: remove prism
	var face_flags: int = param.get("face_flags", 0)

	if (face_flags & 0x180) == 0x180:
		return

	if st2 == null or decoration_size < 1e-3:
		decoration_flags = 0

	# generate points
	var v2: PoolVector2Array = PoolVector2Array()
	if rect.size() > 2:
		v2.append(rect[0])
		v2.append(rect[2])
		v2.append(rect[0] + rect[1] - rect[2])
		v2.append(rect[1])
	else:
		v2.append(rect[0])
		v2.append(Vector2(rect[1].x, rect[0].y))
		v2.append(Vector2(rect[0].x, rect[1].y))
		v2.append(rect[1])

	var v: PoolVector3Array = PoolVector3Array()
	v.append(Vector3(v2[0].x, ys[0], v2[0].y))
	v.append(Vector3(v2[1].x, ys[1], v2[1].y))
	v.append(Vector3(v2[2].x, ys[2], v2[2].y))
	v.append(Vector3(v2[3].x, ys[3], v2[3].y))
	v.append(Vector3(v2[0].x, ys[4], v2[0].y))
	v.append(Vector3(v2[1].x, ys[5], v2[1].y))
	v.append(Vector3(v2[2].x, ys[6], v2[2].y))
	v.append(Vector3(v2[3].x, ys[7], v2[3].y))

	# show prism of -x
	if (face_flags & 0x80) != 0:
		# side faces
		if (face_flags & 0x1) == 0:
			st.add_triangle_fan(PoolVector3Array([v[0], v[4], v[6], v[2]]))
		if (face_flags & 0x40) == 0:
			if (face_flags & 0x6) == 0:
				st.add_triangle_fan(PoolVector3Array([v[0], v[3], v[7], v[4]]))
			if (face_flags & 0x8) == 0:
				st.add_triangle_fan(PoolVector3Array([v[2], v[6], v[7], v[3]]))
		else:
			if (face_flags & 0xA) == 0:
				st.add_triangle_fan(PoolVector3Array([v[1], v[2], v[6], v[5]]))
			if (face_flags & 0x4) == 0:
				st.add_triangle_fan(PoolVector3Array([v[0], v[1], v[5], v[4]]))

		# collision shapes
		if collision_shapes != null:
			var cps: ConvexPolygonShape = ConvexPolygonShape.new()
			if (face_flags & 0x40) == 0:
				cps.points = PoolVector3Array([v[0], v[2], v[3], v[4], v[6], v[7]])
			else:
				cps.points = PoolVector3Array([v[0], v[1], v[2], v[4], v[5], v[6]])
			collision_shapes.append(cps)

	# show prism of +x
	elif (face_flags & 0x100) != 0:
		# side faces
		if (face_flags & 0x2) == 0:
			st.add_triangle_fan(PoolVector3Array([v[1], v[3], v[7], v[5]]))
		if (face_flags & 0x40) == 0:
			if (face_flags & 0x9) == 0:
				st.add_triangle_fan(PoolVector3Array([v[0], v[4], v[7], v[3]]))
			if (face_flags & 0x4) == 0:
				st.add_triangle_fan(PoolVector3Array([v[0], v[1], v[5], v[4]]))
		else:
			if (face_flags & 0x5) == 0:
				st.add_triangle_fan(PoolVector3Array([v[1], v[5], v[6], v[2]]))
			if (face_flags & 0x8) == 0:
				st.add_triangle_fan(PoolVector3Array([v[2], v[6], v[7], v[3]]))

		# collision shapes
		if collision_shapes != null:
			var cps: ConvexPolygonShape = ConvexPolygonShape.new()
			if (face_flags & 0x40) == 0:
				cps.points = PoolVector3Array([v[0], v[1], v[3], v[4], v[5], v[7]])
			else:
				cps.points = PoolVector3Array([v[1], v[2], v[3], v[5], v[6], v[7]])
			collision_shapes.append(cps)

	# show all
	else:
		# side faces
		if (face_flags & 0x1) == 0:
			st.add_triangle_fan(PoolVector3Array([v[0], v[4], v[6], v[2]]))
		if (face_flags & 0x2) == 0:
			st.add_triangle_fan(PoolVector3Array([v[1], v[3], v[7], v[5]]))
		if (face_flags & 0x4) == 0:
			st.add_triangle_fan(PoolVector3Array([v[0], v[1], v[5], v[4]]))
		if (face_flags & 0x8) == 0:
			st.add_triangle_fan(PoolVector3Array([v[2], v[6], v[7], v[3]]))

		# collision shapes
		if collision_shapes != null:
			var cps: ConvexPolygonShape
			if (face_flags & 0x40) == 0:
				if ys[0] - ys[1] - ys[2] + ys[3] < 1e-3 and ys[4] - ys[5] - ys[6] + ys[7] > -1e-3:
					# build convex
					cps = ConvexPolygonShape.new()
					cps.points = v
					collision_shapes.append(cps)
				else:
					# build prism
					cps = ConvexPolygonShape.new()
					cps.points = PoolVector3Array([v[0], v[1], v[3], v[4], v[5], v[7]])
					collision_shapes.append(cps)
					cps = ConvexPolygonShape.new()
					cps.points = PoolVector3Array([v[0], v[2], v[3], v[4], v[6], v[7]])
					collision_shapes.append(cps)
			else:
				if ys[0] - ys[1] - ys[2] + ys[3] > -1e-3 and ys[4] - ys[5] - ys[6] + ys[7] < 1e-3:
					# build convex
					cps = ConvexPolygonShape.new()
					cps.points = v
					collision_shapes.append(cps)
				else:
					# build prism
					cps = ConvexPolygonShape.new()
					cps.points = PoolVector3Array([v[0], v[1], v[2], v[4], v[5], v[6]])
					collision_shapes.append(cps)
					cps = ConvexPolygonShape.new()
					cps.points = PoolVector3Array([v[1], v[2], v[3], v[5], v[6], v[7]])
					collision_shapes.append(cps)

	# bottom face
	if (face_flags & 0x10) == 0:
		_build_bottom_face(v, face_flags, st)

	# top face
	if (face_flags & 0x20) == 0:
		_build_top_face(v, decoration_size, decoration_flags, face_flags, st, st2)

static func build_cube_with_border(param: Dictionary, st: SurfaceTool, st2: SurfaceTool, collision_shapes: Array):
	var origin: Vector3 = param.get("origin", Vector3(0.0, 0.0, 0.0))
	var extent: Vector3 = param.get("extent", Vector3(2.0, 2.0, 2.0))
	var slope: Vector2 = param.get("slope", Vector2(0.0, 0.0))
	var bottom_slope: Vector2 = param.get("bottom_slope", Vector2(0.0, 0.0))
	var border_extent: Vector3 = param.get("border_extent", Vector3(1.0, 0.25, 1.0))

	# bit 0-7: enable border
	# bit 8-11: flip corner face quad
	var border_flags: int = param.get("border_flags", 0)

	# relative size, 0-1
	var decoration_size: float = param.get("decoration_size", 0.2)

	# bit 0-7: show decoration
	var decoration_flags: int = param.get("decoration_flags", 0)

	# bit 0-5: hide faces
	# bit 6-9: remove prism 1,3,7,9
	var face_flags: int = param.get("face_flags", 0)

	if st2 == null or decoration_size < 1e-3:
		decoration_flags = 0

	# shift decoration flags to bit 0-8
	decoration_flags = (decoration_flags & 0xF) | ((decoration_flags & 0xF0) << 1)

	extent.x = max(extent.x, 1e-3)
	extent.y = max(extent.y, 1e-3)
	extent.z = max(extent.z, 1e-3)

	bottom_slope.x = slope.x + min(bottom_slope.x, (extent.y - 1e-3) / extent.x)
	bottom_slope.y = slope.y + min(bottom_slope.y, (extent.y - 1e-3) / extent.z)

	border_extent.x = min(border_extent.x, extent.x * 0.5)
	border_extent.z = min(border_extent.z, extent.z * 0.5)

	if abs(border_extent.y) < 1e-3:
		border_flags = 0

	var xs: Array = []
	var zs: Array = []
	var has_border: Array = []
	var extra_face_flags: Array = []

	xs = [0.0, border_extent.x, extent.x - border_extent.x, extent.x]
	zs = [0.0, border_extent.z, extent.z - border_extent.z, extent.z]
	has_border = [(border_flags & 0x8) != 0, false, false, (border_flags & 0x10) != 0]
	has_border = [[(border_flags & 0x1) != 0, (border_flags & 0x2) != 0, (border_flags & 0x2) != 0, (border_flags & 0x4) != 0], \
		has_border.duplicate(), has_border.duplicate(), \
		[(border_flags & 0x20) != 0, (border_flags & 0x40) != 0, (border_flags & 0x40) != 0, (border_flags & 0x80) != 0]]
	extra_face_flags = [[((border_flags & 0x100) >> 2) | ((face_flags & 0x40) << 2), 0, \
		(((border_flags & 0x200) >> 3) ^ 0x40) | (face_flags & 0x80)], \
		[0, 0, 0], \
		[(((border_flags & 0x400) >> 4) ^ 0x40) | (face_flags & 0x100), 0, \
		((border_flags & 0x800) >> 5) | ((face_flags & 0x200) >> 2)]]

	# test if we can remove x=2
	if ((decoration_flags & 0x6) == 0 or (decoration_flags & 0x6) == 0x6) \
			and (decoration_flags & 0x20) == 0 \
			and ((decoration_flags & 0x180) == 0 or (decoration_flags & 0x180) == 0x180) \
			and (face_flags & 0x280) == 0:
		var b: bool = true
		for v in has_border:
			if v[2] != v[3]:
				b = false
				break
		if b:
			xs.remove(2)
			for v in has_border:
				v.remove(2)
			for v in extra_face_flags:
				v.remove(2)

	# test if we can remove x=1
	if ((decoration_flags & 0x3) == 0 or (decoration_flags & 0x3) == 0x3) \
			and (decoration_flags & 0x8) == 0 \
			and ((decoration_flags & 0xC0) == 0 or (decoration_flags & 0xC0) == 0xC0) \
			and (face_flags & 0x140) == 0:
		var b: bool = true
		for v in has_border:
			if v[0] != v[1]:
				b = false
				break
		if b:
			xs.remove(1)
			for v in has_border:
				v.remove(1)
			for v in extra_face_flags:
				v.remove(0)

	# test if we can remove z=2
	if ((decoration_flags & 0x48) == 0 or (decoration_flags & 0x48) == 0x48) \
			and (decoration_flags & 0x80) == 0 \
			and ((decoration_flags & 0x120) == 0 or (decoration_flags & 0x120) == 0x120) \
			and (face_flags & 0x300) == 0:
		if has_border[2] == has_border[3]:
			zs.remove(2)
			has_border.remove(2)
			extra_face_flags.remove(2)

	# test if we can remove z=1
	if ((decoration_flags & 0x9) == 0 or (decoration_flags & 0x9) == 0x9) \
			and (decoration_flags & 0x2) == 0 \
			and ((decoration_flags & 0x24) == 0 or (decoration_flags & 0x24) == 0x24) \
			and (face_flags & 0xC0) == 0:
		if has_border[0] == has_border[1]:
			zs.remove(1)
			has_border.remove(1)
			extra_face_flags.remove(0)

	var xmax: int = xs.size() - 2
	var zmax: int = zs.size() - 2

	var df: Array = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

	df[0][0] |= decoration_flags & 0x1
	df[0][xmax] |= decoration_flags & 0x4
	df[zmax][0] |= decoration_flags & 0x40
	df[zmax][xmax] |= decoration_flags & 0x100
	for i in xmax + 1:
		df[0][i] |= (decoration_flags & 0x2) | \
			((decoration_flags & 0x2) >> 1 if i > 0 else 0) | \
			((decoration_flags & 0x2) << 1 if i < xmax else 0)
		df[zmax][i] |= (decoration_flags & 0x80) | \
			((decoration_flags & 0x80) >> 1 if i > 0 else 0) | \
			((decoration_flags & 0x80) << 1 if i < xmax else 0)
	for j in zmax + 1:
		df[j][0] |= (decoration_flags & 0x8) | \
			((decoration_flags & 0x8) >> 3 if j > 0 else 0) | \
			((decoration_flags & 0x8) << 3 if j < zmax else 0)
		df[j][xmax] |= (decoration_flags & 0x20) | \
			((decoration_flags & 0x20) >> 3 if j > 0 else 0) | \
			((decoration_flags & 0x20) << 3 if j < zmax else 0)

	for zidx in zmax + 1:
		if zs[zidx + 1] - zs[zidx] < 1e-3:
			continue
		for xidx in xmax + 1:
			if xs[xidx + 1] - xs[xidx] < 1e-3:
				continue
			build_cube({
				rect = PoolVector2Array([Vector2(origin.x + xs[xidx],
					origin.z + zs[zidx]),
					Vector2(origin.x + xs[xidx + 1],
					origin.z + zs[zidx + 1])]),
				ys = PoolRealArray([origin.y + xs[xidx] * bottom_slope.x + zs[zidx] * bottom_slope.y,
					origin.y + xs[xidx + 1] * bottom_slope.x + zs[zidx] * bottom_slope.y,
					origin.y + xs[xidx] * bottom_slope.x + zs[zidx + 1] * bottom_slope.y,
					origin.y + xs[xidx + 1] * bottom_slope.x + zs[zidx + 1] * bottom_slope.y,
					origin.y + extent.y + xs[xidx] * slope.x + zs[zidx] * slope.y
						+ (border_extent.y if has_border[zidx][xidx] else 0.0),
					origin.y + extent.y + xs[xidx + 1] * slope.x + zs[zidx] * slope.y
						+ (border_extent.y if has_border[zidx][xidx + 1] else 0.0),
					origin.y + extent.y + xs[xidx] * slope.x + zs[zidx + 1] * slope.y
						+ (border_extent.y if has_border[zidx + 1][xidx] else 0.0),
					origin.y + extent.y + xs[xidx + 1] * slope.x + zs[zidx + 1] * slope.y
						+ (border_extent.y if has_border[zidx + 1][xidx + 1] else 0.0)]),
				decoration_size = decoration_size,
				decoration_flags = df[zidx][xidx],
				face_flags = (face_flags & 0x3F) | (1 if xidx > 0 else 0) | (2 if xidx < xmax else 0) \
					| (4 if zidx > 0 else 0) | (8 if zidx < zmax else 0) \
					| extra_face_flags[zidx][xidx],
			}, st, st2, collision_shapes)

static func _build_capsule_head(p: Transform, radius: float, \
		radial_segments: int, rings_half: int, inverted: bool, st: SurfaceTool):

	var b: float = 0.0
	var sgn: float = -1.0 if inverted else 1.0

	for j in rings_half:
		var b2: float = ((j + 1) as float) / rings_half * 0.5 * PI

		var v0: Vector3 = radius * Vector3(cos(b), 0.0, sin(b) * sgn)
		var v02: Vector3 = radius * Vector3(cos(b2), 0.0, sin(b2) * sgn)

		var pt1: Vector3 = p.xform(v0)
		var pt2: Vector3 = p.xform(v02)

		for i in radial_segments:
			var a: float = ((i + 1 - radial_segments) as float) / radial_segments * 2.0 * PI
			var cos_a: float = cos(a)
			var sin_a: float = sin(a)
			var pt1_new: Vector3 = p.xform(Vector3(cos_a * v0.x, sin_a * v0.x, v0.z))
			if j < rings_half - 1:
				var pt2_new: Vector3 = p.xform(Vector3(cos_a * v02.x, sin_a * v02.x, v02.z))
				st.add_triangle_fan(PoolVector3Array([pt2, pt1, pt1_new, pt2_new] \
					if inverted else [pt1, pt2, pt2_new, pt1_new]))
				pt2 = pt2_new
			else:
				st.add_triangle_fan(PoolVector3Array([pt2, pt1, pt1_new] \
					if inverted else [pt1, pt2, pt1_new]))
			pt1 = pt1_new

		b = b2

static func _build_capsule(p1: Transform, p2: Transform, radius: float, \
		radial_segments: int, rings_half: int, flags: int, \
		st: SurfaceTool, collision_shapes: Array):

	var v: Vector3 = Vector3(radius, 0.0, 0.0)
	var pt1: Vector3 = p1.xform(v)
	var pt2: Vector3 = p2.xform(v)

	for i in radial_segments:
		var a: float = ((i + 1 - radial_segments) as float) / radial_segments * 2.0 * PI
		v = radius * Vector3(cos(a), sin(a), 0.0)
		var pt1_new: Vector3 = p1.xform(v)
		var pt2_new: Vector3 = p2.xform(v)
		st.add_triangle_fan(PoolVector3Array([pt1, pt2, pt2_new, pt1_new]))
		pt1 = pt1_new
		pt2 = pt2_new

	if (flags & 1) != 0 and rings_half > 0:
		_build_capsule_head(p1, radius, radial_segments, rings_half, true, st)
	if (flags & 2) != 0 and rings_half > 0:
		_build_capsule_head(p2, radius, radial_segments, rings_half, false, st)

	if collision_shapes != null:
		var z_vector: Vector3 = p1.origin - p2.origin
		var shape: CapsuleShape = CapsuleShape.new()
		shape.height = z_vector.length()
		shape.radius = radius
		z_vector = z_vector.normalized()
		var x_vector: Vector3
		match z_vector.abs().min_axis():
			Vector3.AXIS_X:
				x_vector = Vector3(1.0, 0.0, 0.0)
			Vector3.AXIS_Y:
				x_vector = Vector3(0.0, 1.0, 0.0)
			Vector3.AXIS_Z:
				x_vector = Vector3(0.0, 0.0, 1.0)
		var y_vector: Vector3 = z_vector.cross(x_vector)
		collision_shapes.append([shape, \
			Transform(x_vector, y_vector, z_vector, (p1.origin + p2.origin) * 0.5)])

# NOTE: z_vector must be normalized
static func _create_basis(y_vector: Vector3, z_vector: Vector3) -> Basis:
	var x_vector: Vector3 = y_vector.cross(z_vector).normalized()
	return Basis(x_vector, z_vector.cross(x_vector), z_vector)

static func build_rail(param: Dictionary, st: SurfaceTool, collision_shapes: Array):
	st.add_smooth_group(true)

	var origin: Vector3 = param.get("origin", Vector3(0.0, 0.0, 0.0))

	var radius: float = param.get("radius", 0.14)

	var offsets: PoolVector3Array = param.get("offsets", \
		PoolVector3Array([Vector3(0.76, 0.0, 0.0), Vector3(-0.76, 0.0, 0.0)]))

	if offsets.size() < 1:
		offsets = PoolVector3Array([Vector3(0.0, 0.0, 0.0)])

	var radial_segments: int = param.get("radial_segments", 16)
	var rings_half: int = param.get("rings_half", 4)

	var y_vector: Vector3 = param.get("y_vector", Vector3(0.0, 1.0, 0.0))
	if y_vector.length_squared() < 1e-3:
		y_vector = Vector3(0.0, 1.0, 0.0)
	else:
		y_vector = y_vector.normalized()

	# bit 0: z vector depends on two neighborhood points
	var flags: int = param.get("flags", 0)

	var hide_head: int = param.get("hide_head", 0)

	var segments: Array = param.get("segments", [])

	var my_points: PoolVector3Array = PoolVector3Array()
	var my_y_vectors: PoolVector3Array = PoolVector3Array()
	var my_z_vectors: PoolVector3Array = PoolVector3Array()

	# add the very first point
	my_points.append(origin)
	my_y_vectors.append(y_vector)
	my_z_vectors.append(param.get("z_vector", Vector3(0.0, 0.0, 0.0)))

	# add remaining points
	for i in segments.size():
		var p: Dictionary = segments[i]
		my_points.append(origin + p.get("position", Vector3(0.0, 0.0, 0.0)))
		my_y_vectors.append(p.get("y_vector", Vector3(0.0, 0.0, 0.0)))
		my_z_vectors.append(p.get("z_vector", Vector3(0.0, 0.0, 0.0)))

	for i in my_points.size():
		if my_y_vectors[i].length_squared() < 1e-3:
			my_y_vectors[i] = y_vector
		else:
			my_y_vectors[i] = my_y_vectors[i].normalized()

		if my_z_vectors[i].length_squared() < 1e-3:
			if (flags & 0x1) != 0:
				# z vector depends on two neighborhood points
				if i > 0:
					my_z_vectors[i] += (my_points[i] - my_points[i - 1]).normalized()
				if i < my_points.size() - 1:
					my_z_vectors[i] += (my_points[i + 1] - my_points[i]).normalized()
			else:
				# z vector only depends on one neighborhood point
				var ii: int = i if i > 0 else 1
				my_z_vectors[i] += (my_points[ii] - my_points[ii - 1]).normalized()
		my_z_vectors[i] = my_z_vectors[i].normalized()

	var my_hide_segment: PoolIntArray = PoolIntArray()
	var offsets_prev_size: int = offsets.size()

	for i in segments.size():
		var p: Dictionary = segments[i]
		var offsets_size: int = p.get("offsets").size() if p.has("offsets") else 0
		offsets_size = max(offsets_size, offsets.size()) as int
		my_hide_segment.append(p.get("hide_segment", 0) | \
			-(1 << (min(offsets_size, offsets_prev_size) as int)))
		offsets_prev_size = offsets_size

	# build segments
	var offsets_prev: PoolVector3Array = offsets

	for i in segments.size():
		var p: Dictionary = segments[i]

		var type: String = p.get("type", "bezier")

		var y_vector_rotate_laps: int = p.get("y_vector_rotate_laps", 0)

		var segment_count: int = max(p.get("segment_count", 1), 1) as int

		var hide_segment_prev: int = my_hide_segment[i - 1] if i > 0 else -1
		var hide_segment: int = my_hide_segment[i]
		var hide_segment_next: int = my_hide_segment[i + 1] if i < segments.size() - 1 else -1
		var hide_head_2: int = p.get("hide_head", 0)

		var offsets_cur: PoolVector3Array = PoolVector3Array()
		if p.has("offsets"):
			offsets_cur = p.get("offsets")
		while offsets_cur.size() < offsets.size():
			offsets_cur.append(offsets[offsets_cur.size()])

		offsets_prev_size = min(offsets_prev.size(), offsets_cur.size()) as int

		var f1: float = 0.0
		var b1: Basis = _create_basis(my_y_vectors[i], my_z_vectors[i])
		var p1: Vector3 = my_points[i]
		var dp_len: float = (my_points[i + 1] - p1).length()

		# bezier only
		var control1: Vector3 = (p.get("control1", 1.0) * dp_len) * my_z_vectors[i]
		var control2: Vector3 = (p.get("control2", 1.0) * dp_len) * my_z_vectors[i + 1]

		# rotate only
		var rotate_center: Vector3 = origin + p.get("rotate_center", Vector3(0.0, 0.0, 0.0))
		var rotate_axis: Vector3 = p.get("rotate_axis", Vector3(0.0, 1.0, 0.0))
		var rotate_angle: float = 0.0
		if type == "rotate":
			if rotate_axis.length_squared() < 1e-3:
				rotate_axis = Vector3(0.0, 1.0, 0.0)
			else:
				rotate_axis = rotate_axis.normalized()
			var rotate_p1: Vector3 = (Geometry.get_closest_point_to_segment_uncapped(my_points[i], \
				rotate_center, rotate_center + rotate_axis) - my_points[i]).normalized()
			var rotate_p2: Vector3 = (Geometry.get_closest_point_to_segment_uncapped(my_points[i + 1], \
				rotate_center, rotate_center + rotate_axis) - my_points[i + 1]).normalized()
			rotate_angle = acos(clamp(rotate_p1.dot(rotate_p2), -1.0, 1.0))
			if rotate_p1.cross(rotate_p2).dot(rotate_axis) < 0.0:
				rotate_angle = -rotate_angle
			rotate_angle += p.get("rotate_laps", 0) * 2.0 * PI

		for step in segment_count:
			var f2: float = ((step + 1) as float) / segment_count
			var b2y: Vector3
			var b2y_new: Vector3
			var b2z: Vector3
			var p2: Vector3

			match type:
				"rotate":
					var a1: float = rotate_angle * f2
					var a2: float = rotate_angle * (f2 - 1.0)
					var bb1: Basis = Basis(rotate_axis, a1)
					var bb2: Basis = Basis(rotate_axis, a2)
					p2 = lerp(bb1.xform(my_points[i] - rotate_center), \
						bb2.xform(my_points[i + 1] - rotate_center), f2) + rotate_center
					b2z = bb1.xform(my_z_vectors[i])
					var b2z_new: Vector3 = bb2.xform(my_z_vectors[i + 1])
					if b2z.is_equal_approx(b2z_new):
						pass
					elif b2z.is_equal_approx(-b2z_new):
						# oops
						pass
					else:
						b2z = b2z_new.slerp(b2z, 1.0 - f2)
					b2y = bb1.xform(my_y_vectors[i])
					b2y_new = bb2.xform(my_y_vectors[i + 1])
				_: # default is bezier
					var f3: float = f2 - 1.0
					p2 = (f3 * f3) * ((1.0 + 2.0 * f2) * my_points[i] + f2 * control1) \
						+ (f2 * f2) * ((3.0 - 2.0 * f2) * my_points[i + 1] + f3 * control2)
					b2z = (6.0 * f2 * f3) * (my_points[i] - my_points[i + 1]) \
						+ (f3 * (3.0 * f2 - 1.0)) * control1 + (f2 * (3.0 * f2 - 2.0)) * control2
					b2z = b2z.normalized()
					b2y = my_y_vectors[i]
					b2y_new = my_y_vectors[i + 1]

			if b2y.is_equal_approx(b2y_new):
				pass
			elif b2y.is_equal_approx(-b2y_new):
				b2y = b2y_new.rotated(b2z, (1.0 - f2) * PI)
			else:
				b2y = b2y_new.slerp(b2y, 1.0 - f2)
			b2y = b2y.rotated(b2z, y_vector_rotate_laps * (f2 - 1.0) * 2.0 * PI)

			var b2: Basis = _create_basis(b2y, b2z)

			for j in offsets_prev_size:
				if (hide_segment & (1 << j)) != 0:
					continue
				var fl: int = 0
				if (hide_head & (1 << j)) == 0 and (hide_segment_prev & (1 << j)) != 0 and step == 0:
					fl |= 1
				if (hide_head_2 & (1 << j)) == 0 and (hide_segment_next & (1 << j)) != 0 and step == segment_count - 1:
					fl |= 2

				var offset1: Vector3 = lerp(offsets_prev[j], offsets_cur[j], f1)
				var offset2: Vector3 = lerp(offsets_prev[j], offsets_cur[j], f2)
				var o1: Vector3 = p1 + b1.xform(offset1)
				var o2: Vector3 = p2 + b2.xform(offset2)
				_build_capsule(Transform(b1, o1), Transform(b2, o2), radius, \
					radial_segments, rings_half, fl, st, collision_shapes)

			f1 = f2
			b1 = b2
			p1 = p2

		hide_head = hide_head_2
		offsets_prev = offsets_cur

static func build_from_type(param: Dictionary, st: SurfaceTool, st2: SurfaceTool, collision_shapes: Array):
	match param.get("type"):
		"cube":
			build_cube(param, st, st2, collision_shapes)
		"cube_with_border":
			build_cube_with_border(param, st, st2, collision_shapes)
		"rail":
			build_rail(param, st, collision_shapes)
